package Tree;

import com.sun.source.tree.Tree;
import org.w3c.dom.NodeList;

import javax.swing.event.UndoableEditListener;

public class Search {
  static class TreeNode{
      public int val;
      public TreeNode left;
      public TreeNode right;

      public TreeNode(int val){
          this.val = val;
      }


  }


  public TreeNode root = null;
  public boolean search(int val){
      TreeNode cur = root;
      if (cur == null){
          return false;
      }
      while (cur != null){
          if(val < cur.val){
              cur = cur.left;
          }else if(val > cur.val){
              cur = cur.right;
          }else{
              return true;
          }
      }
      return false;
  }


  public boolean insesr(int val){
      TreeNode parent = null;
      TreeNode cur = root;
      TreeNode node = new TreeNode(val);
      if (root == null){
          root = node;
          return true;
      }

      while(cur != null){
          if(val > cur.val){
              parent =  cur;
              cur =  cur.right;
          }else if(val < cur.val){
              parent = cur;
              cur = cur.left;
          }else{
              return false;
          }
      }

      if(val >  parent.val){
          parent.right = node;
          return true;
      }else{
          parent.left = node;
          return true;
      }

  }


  public boolean remove(int val){
      TreeNode cur = root;
      TreeNode parent = null;
      while(cur != null){
          if(val > cur.val){
              parent = cur;
              cur = cur.right;
          }else if(val < cur.val){
              parent = cur;
              cur = cur.left;
          }else{
              break;
          }
      }

      if(cur == null){
          return false;
      }

      if(cur.left == null &&  cur.right == null){
          if(cur == root){
              root = null;
              return true;
          } else if (cur == parent.left){
              parent.left = null;
          }else{
              parent.right = null;
          }
      }else if(cur.left == null || cur.right == null){
          TreeNode child  = (cur.left != null) ? cur.left : cur.right;
          if(cur == root){
              root = child;
          }else if(cur == parent.left){
              parent.left = child;
          }else{
              parent.right = child;
          }
      }else{
          TreeNode min = findMin(cur.right);
          cur.val = min.val;
          remove(min.val);
      }
      return true;
  }

  public TreeNode findMin(TreeNode node){
      while(node.left != null){
          node = node.left;
      }
      return node;
  }
}
